home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / plane / _Segment1.c.ORG < prev    next >
Encoding:
Text File  |  1994-11-16  |  5.8 KB  |  262 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _Segment1.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. //#include <LEDA/line.h>
  18.  
  19. #include <LEDA/Segment1.h>
  20. #include <math.h>
  21. #include <ctype.h>
  22.  
  23. //static const double eps = 1e-10;
  24.  
  25.  
  26. //------------------------------------------------------------------------------
  27. // Segments 
  28. //------------------------------------------------------------------------------
  29.  
  30. Segment_rep::Segment_rep()  { count = 1; }
  31.  
  32. Segment_rep::Segment_rep(const Point& p, const Point& q) 
  33. { start = p;
  34.   end   = q;
  35.   dx = q.X()*p.W() - p.X()*q.W();
  36.   dy = q.Y()*p.W() - p.Y()*q.W();
  37.   count = 1; 
  38.     
  39. }
  40.   
  41.  
  42.  
  43. Segment::Segment() { PTR = new Segment_rep; }
  44.  
  45. Segment::Segment(const Point& x, const Point& y) 
  46. { PTR = new Segment_rep(x,y); }
  47.  
  48. Segment::Segment(const Int& x1, const Int& y1, const Int& x2, const Int& y2) 
  49. { PTR = new Segment_rep(Point(x1,y1), Point(x2,y2)); }
  50.  
  51.  
  52. /*
  53. Segment::Segment(const Point& p, double alpha, double length)
  54. { Point q = p.translate(alpha,length);
  55.   PTR  = new Segment_rep(p,q); 
  56.  }
  57.   
  58. Segment Segment::translate(double alpha, double d) const
  59. { Point p = ptr()->start.translate(alpha,d);
  60.   Point q = ptr()->end.translate(alpha,d);
  61.   return Segment(p,q);
  62.  }
  63.  
  64. Segment Segment::translate(const vector& v) const
  65. { Point p = ptr()->start.translate(v);
  66.   Point q = ptr()->end.translate(v);
  67.   return Segment(p,q);
  68.  }
  69.  
  70. */
  71.  
  72.  
  73. ostream& operator<<(ostream& out, const Segment& s) 
  74. { out << "[" << s.start() << "===" << s.end() << "]"; 
  75.   return out;
  76.  } 
  77.  
  78. /*
  79. istream& operator>>(istream& in, Segment& s) 
  80. { int x1,x2,y1,y2; 
  81.   in >> x1 >> y1 >> x2 >> y2; 
  82.   s = Segment(Point(x1,y1),Point(x2,y2)); 
  83.   return in; 
  84.  } 
  85. */
  86.  
  87. istream& operator>>(istream& in, Segment& s) 
  88. { // syntax: {[} p {===} q {]}
  89.  
  90.   Point p,q; 
  91.   char c;
  92.  
  93.   do in.get(c); while (isspace(c));
  94.   if (c != '[') in.putback(c);
  95.  
  96.   in >> p;
  97.  
  98.   do in.get(c); while (isspace(c));
  99.   while (c== '=') in.get(c);
  100.   while (isspace(c)) in.get(c);
  101.   in.putback(c);
  102.  
  103.   in >> q; 
  104.  
  105.   do in.get(c); while (c == ' ');
  106.   if (c != ']') in.putback(c);
  107.  
  108.   s = Segment(p,q); 
  109.   return in; 
  110.  
  111.  } 
  112.  
  113.  
  114. /*
  115. double Segment::angle(const Segment& s) const
  116. {
  117.   double cosfi,fi,norm;
  118.   
  119.   double dx  = ptr()->end.ptr()->x - ptr()->start.ptr()->x; 
  120.   double dy  = ptr()->end.ptr()->y - ptr()->start.ptr()->y; 
  121.  
  122.   double dxs = s.ptr()->end.ptr()->x - s.ptr()->start.ptr()->x; 
  123.   double dys = s.ptr()->end.ptr()->y - s.ptr()->start.ptr()->y; 
  124.   
  125.   cosfi=dx*dxs+dy*dys;
  126.   
  127.   norm=(dx*dx+dy*dy)*(dxs*dxs+dys*dys);
  128.  
  129.   if (norm == 0) return 0;
  130.  
  131.   cosfi /= sqrt( norm );
  132.  
  133.   if (cosfi >=  1.0 ) return 0;
  134.   if (cosfi <= -1.0 ) return M_PI;
  135.   
  136.   fi=acos(cosfi);
  137.  
  138.   if (dx*dys-dy*dxs>0) return fi;
  139.  
  140.   return -fi;
  141.  
  142. }
  143.  
  144.  
  145. double Segment::distance(const Segment& s) const
  146. { if (angle(s)!=0) return 0;
  147.   return distance(s.ptr()->start);
  148.  }
  149.  
  150. double  Segment::distance() const
  151. { return distance(Point(0,0)); }
  152.  
  153. double Segment::distance(const Point& p) const
  154. { Segment s(ptr()->start,p);
  155.   double l = s.length();
  156.   if (l==0) return 0;
  157.   else return l*sin(angle(s));
  158.  }
  159.  
  160.  
  161. double  Segment::y_proj(double x)  const
  162. { return  ptr()->start.ptr()->y - ptr()->slope * (ptr()->start.ptr()->x - x); }
  163.  
  164. double  Segment::x_proj(double y)  const
  165. { if (vertical())  return  ptr()->start.ptr()->x;
  166.   return  ptr()->start.ptr()->x - (ptr()->start.ptr()->y - y)/ptr()->slope; }
  167.  
  168. */
  169.  
  170. bool Segment::intersection(const Segment& s, Point& inter) const
  171. /* decides whether |s| and |this| segment intersect and, if so, returns the
  172. intersection in |r|. It is assumed that both segments have non-zero length */
  173. { 
  174. Int px = ptr()->start.X();
  175. Int py = ptr()->start.Y();
  176. Int pw = ptr()->start.W();
  177.  
  178. Int qx = ptr()->end.X();
  179. Int qy = ptr()->end.Y();
  180. Int qw = ptr()->end.W();
  181.  
  182. Int spx = s.start().X();
  183. Int spy = s.start().Y();
  184. Int spw = s.start().W();
  185.  
  186. Int sqx = s.end().X();
  187. Int sqy = s.end().Y();
  188. Int sqw = s.end().W();
  189.  
  190. Int A = -(py*qw - qy*pw);
  191. Int B =   px*qw - qx*pw;
  192. Int C = -(px*qy - qx*py);
  193.  
  194.  
  195. Int Aprime = -(spy*sqw - sqy*spw);
  196. Int Bprime =   spx*sqw - sqx*spw;
  197. Int Cprime = -(spx*sqy - sqx*spy);
  198.  
  199. Int cx = -(B*Cprime - C*Bprime);
  200. Int cy =   A*Cprime - C*Aprime ;
  201. Int cw = -(A*Bprime - B*Aprime);
  202.  
  203. if (cw == 0) return false;   //same slope
  204.  
  205. inter = Point(cx,cy,cw);
  206.  
  207.  
  208. /* cw is non-zero. Its sign does not matter for the test to follow.
  209.  
  210.   
  211.   if (pX*cw < cx &&  qX*cw < cx ||  pX*cw > cx  && qX*cw > cx ||
  212.    spX*cw< cx && sqX*cw < cx || spX*cw > cx && sqX*cw > cx ||
  213.    pY*cw < cy &&  qY*cw < cy ||  pY*cw > cy  && qY*cw > cy ||
  214.    spY*cw< cy && sqY*cw < cy || spY*cw > cy && sqY*cw > cy)
  215.   return false;
  216. */
  217.  
  218. /* we still need to test whether inter lies on both segments. A point lies on a segment if it compares diffently with the two endpoints of the segment */
  219.  
  220. if ((compare(start(),inter) == compare(end(),inter)) ||
  221.  (compare(s.start(),inter) == compare(s.end(),inter)))
  222. return false;
  223.  
  224. return true;
  225. }
  226.  
  227.  
  228. bool Segment::intersection_of_lines(const Segment& s, Point& inter) const
  229. { 
  230.   /* decides whether the lines induced by |s| and |this| segment 
  231.      intersect and, if so, returns the intersection in |inter|. 
  232.      It is assumed that both segments have non-zero length
  233.    */
  234.   
  235.   Int w = dy()*s.dx() - dx()*s.dy();
  236.  
  237.   if (w == 0) return false;   //same slope
  238.  
  239.   Int c1 = X2()*Y1() - X1()*Y2();
  240.   Int c2 = s.X2()*s.Y1() - s.X1()*s.Y2();
  241.  
  242.   inter = Point(dx()*c2 - s.dx()*c1, dy()*c2 - s.dy()*c1, w);
  243.  
  244.   return true;
  245. }
  246.  
  247. /*
  248. Segment Segment::rotate(double alpha) const
  249. {  double  l = length();
  250.    Point p = start();
  251.    double beta = alpha + angle();
  252.    return Segment(p,beta,l);
  253. }
  254.  
  255. Segment Segment::rotate(const Point& origin, double alpha) const
  256. {  Point p = start().rotate(origin,alpha);
  257.    Point q = end().rotate(origin,alpha);
  258.    return Segment(p,q);
  259. }
  260. */
  261.  
  262.